package unclassified.medium;

import java.util.*;

/**
 * 外观数列
 * 一步一步来
 *
 * 给一个数，这个数是1
 * 描述上一步的数，这个数是 1 即一个1，故写作11
 * 描述上一步的数，这个数是11即两个1，故写作21
 * 描述上一步的数，这个数是21即一个2一个1，故写作12-11
 * 描述上一步的数，这个数是1211即一个1一个2两个1，故写作11-12-21
 * 示例 1：
 *
 * 输入：n = 1
 * 输出："1"
 * 解释：这是一个基本样例。
 * 示例 2：
 *
 * 输入：n = 4
 * 输出："1211"
 * 解释：
 * countAndSay(1) = "1"
 * countAndSay(2) = 读 "1" = 一 个 1 = "11"
 * countAndSay(3) = 读 "11" = 二 个 1 = "21"
 * countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-and-say
 */
public class CountAndSay_38 {

    public String countAndSay(int n) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        for (int i = 2; i <= n; i++) {

            int size = queue.size();
            while (size-- > 0) {
                Integer poll = queue.poll();
                int count = 1;
                while (!queue.isEmpty() && size != 0 && queue.peek().equals(poll) ) {
                    count++;
                    queue.poll();
                    size--;
                }
                queue.offer(count);
                queue.offer(poll);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()) {
            sb.append(queue.poll());
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        CountAndSay_38 ca = new CountAndSay_38();
        System.out.println(ca.countAndSay(5));
    }
}
